"""
* AcWing 503. 借教室
* 一杯茶，一壶酒，一道算法，一下午
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
* 本题是一道以二分法为重要的算法考点的题目
* 本题会涉及到两种思维，一种是差分思想，具体可以看Acwing 797.差分 或者洛谷的P8218 【深进1.例1】求区间和
* 另一种是二分思想，主要是对二分查找算法是应用，具体可以看Acwing 789.数的范围 或者洛谷的P2249 【深基13.例1】查找
* 但是上面这两题需要买算法基础课才可以解锁

* 如果判定时间是1s的话，想要不超时的情况下，算法的时间复杂度的规模应该控制在小于10^8
* 本题如果直接暴力的话，复杂度是O(mn) 也就是10^6 * 10^6 = 10^12所以是需要优化的

* 以下是对本题进行差分思想来解题的分析阐述：
* 但是这一题可以转化为一道判定性的问题 -> 判断是否能处理前K个订单？ -> 判定性问题需要用差分思想来做。
* 也就是说，当订单的个数k已经确定的时候，每天需要租借的教室的数目也就确定了，
* -> 这时候我们首先已知数组rooms，代表每天可以租借的教室的个数；
* -> 然后我们可以定义另一个数组，needs，表示每天需要租借的教室的数目，
* 这时候我们只需要逐一比较每天可借是否一一满足每天续借教室数就可以判定当前确定的订单数k,是否是可以被处理的订单临界值
* -> 但是很显然，needs数组的每个元素的值会随着订单数的改变而逐一改变，这样就相当于又需要一个多余的循环来构造needs数组，而这就是暴力法的做法。
* 而使用差分法的点就在于，我们对needs数组采用差分的思想来进行分析（数学原理见笔记截图），构造出needs数组的差分数组differ_needs
* 差分数组的相减的特性，使得对于原needs数组因订单次数改变而会发生部分区间的元素改变的特性在新的差分数组上的大部分元素上被抵消了，只留下了两个数会变化，
* -> 而差分数组本身又和原数组具备一定的信息量，即原素组是差分数组的前缀和数组，所以只要知道差分数组，就可以求原数组
* 因此我们可以把订单的变化对原数组的每个元素的影响，映射到对差分数组的仅两个数的影响，先计算出差分数组，再转求最后的原数组来比较判定即可。
------------------------------------------------------
* 以下是对本题进行二分查找思想来解题的分析阐述：
* 我们可以假设，第k个订单是可以满足借教室情况的最后一个订单，那么第k+1个订单就是第一个没办法满足借教室的需求的订单
* -> 为了提高搜索k值的效率或者判断是否存在这个k值的效率，我们决定使用二分查找的方式来加速查找。
* -> 对于订单区间[1,m]，k属于[1,m]，我们要找到最后一个满足需求的订单号k，也就是说，k之前的订单号也都是可以满足的，当我们找到一个可以满足的k之后，
* 我们应该向右（后）继续寻找其他也可以满足需求的订单号，直到找到最后一个满足需求的订单号k
* -> 反之，如果当前我们找的mid已经不满足需求了，那我们就得往订单区间的左边再去找一找，找更靠前的订单号。
* 一般来说，二分查找需要满足的条件是，查找的序列（区间）应该是一个单调不减的序列（区间），这里我们找的是1到m,本身就是单调不减的，所以就不需要进行排序。
"""


def resolution1():
    # n为天数，m为订单总数：
    n, m = map(int, input().split())
    # 获取明天的教室的数量数组：
    # -> 原数组下标为0的元素进行补零填充，这样真正的a1就是从下标为1的元素开始了。
    rooms = [0]
    rooms.extend(list(map(int, input().split())))
    # 一一比对订单的情况
    # -> end用来控制是否结束
    end = False
    for j in range(1, m+1):
        dj, sj, tj = map(int, input().split())
        for day in range(sj, tj+1):
            rooms[day] -= dj
            if rooms[day] < 0:
                end = True
                break
        if end:
            # 宣布借教室失败
            print(-1)
            # 在失败的订单号处宣布
            print(j)
            break
    if not end:
        print(0)


def resolution2():
    # input
    day, order = map(int, input().split())
    rooms = [0]
    rooms.extend(list(map(int, input().split())))
    # 输入订单信息
    order_rooms = [0] * (order+1)
    start_times = [0] * (order+1)
    end_times = [0] * (order+1)
    for i in range(1, order+1):
        order_rooms[i], start_times[i], end_times[i] = map(int, input().split())

    # 在订单数列上二分查找最后一个满足租借需求的订单序号
    left = 0
    right = order
    while left < right:
        # 因为left是从0开始的，所以真正的范围区间应该是[left+1, right]
        mid = left + 1 + right >> 1
        # 若当前的mid序号的订单可以满足需求的话，那就往右边继续找下一个可以满足的
        # 因为mid也满足，所以要保留mid在内
        if judge(mid, rooms, order_rooms, start_times, end_times, day):
            left = mid
        else:
            right = mid - 1
    # 如果最后一个可以满足的订单的序号刚好是最后一个订单的话，说明所有的订单都可以满足，
    # 反之，则必然存在不能满足的情况
    if right == order:
        print(0)
    else:
        print(f"-1\n{(right + 1)}")



"""
* mid为当前二分查找的订单编号值
* rooms为每天所能提供的教室的数组
* order_rooms为每个订单要求租借的房间数
* start_times为每个订单开始时间
* end_times为每个订单的结束时间
* day为总天数
"""
def judge(mid, rooms, order_rooms, start_times, end_times, day):
    # 先构建并初始化需求数组的差分数组
    # 当处理的是第0个订单的时候，需求数组的所有元素的值都是0，自然差分数组的所有的值也都是0
    differ_needs = [0] * (day+1+1)
    # 针对订单数来求差分数组
    for i in range(1, mid+1):
        differ_needs[start_times[i]] += order_rooms[i]
        differ_needs[end_times[i]+1] -= order_rooms[i]
    # 基于差分数组求需求数组，逐天比较是否满足条件
    needs = [0] * (day+1)
    for i in range(1, day+1):
        # 原始数组是差分数组的前缀和数组
        needs[i] = differ_needs[i] + needs[i-1]
        if needs[i] > rooms[i]:
            return False
    return True


if __name__ == '__main__':
    # resolution1为暴力搜索法
    # resolution1()
    # resolution2为差分+二分搜索方法
    resolution2()